\documentclass[11pt,letterpaper]{article}

\newcommand{\mytitle}{CS254 Midterm}
\newcommand{\myauthor}{Kevin Lewi}
\date{February 17, 2012}

\newcommand{\size}{\operatorname{Size}}
\newcommand{\poly}{\operatorname{poly}}

\usepackage{hwformat}

\begin{document}

\maketitle

\section*{Problem 1}

\section*{Problem 2}

For the first claim, note that for $k$ adaptive queries, consider the $i$th 
query. It outputs either YES or NO, and the $i$th query is thus a function of 
the outputs of the previous queries. We can thus construct a perfect binary tree 
of $k$ levels, where the query at the $i$th level of this binary tree is a 
function of the outputs of the queries that happened before it. There are exact 
$2^k-1$ nodes in this binary, and we simply make one query for each node, all in 
parallel.

For the second claim, we can interpret the output of the $2^k-1$ parallel 
queries as some member of $\{0,1\}^{2^k-1}$. Let $s$ represent this string. We 
will use the first $k$ adaptive queries to determine the number of ones (or, 
queries that outputted YES) in $s$. This will only take $k$ adaptive queries 
because the number of ones in $s$ is in the interval $[0,2^k-1]$, and one can 
use binary search to determine the exact number in only $k$ queries. Let the 
number of ones in $s$ be called $x$.

Now, let $f$ be the poly-time computable function that is used to parse the 
$2^k-1$ parallel queries. We can now construct the following problem to pass to 
the NP oracle as our very last query: given as input $f$, the encodings of the 
$2^{k-1}$ parallel queries, and the integer $x$, determine if there exists a 
string $s'$ such that $f(s')$ outputs YES, $s'$ has exactly $x$ ones, and $s'$ 
agrees with the YES/NO decisions made by the $2^{k-1}$ parallel queries. This 
problem is solvable by the NP oracle because if the answer to this problem is 
YES, then that means there exists some $s'$ with all of the above properties, 
and all of the above properties are indeed checkable in polynomial time. 
Otherwise, there does not exist such an $s'$, and we output NO correctly.

This last query, along with the first $k$ queries to determine the number of 
ones in $s$, means that we used $k+1$ adaptive queries to simulate the $2^k-1$ 
parallel queries.

\section*{Problem 3}

we know from one of the lectures about Adleman's theorem, which states that if 
$L \in BPP$ then $L$ can be determined by a family of polynomial-sized circuits. 
In other words, $BPP \subseteq \size(\poly(n))$.

Now, recall that there is a such thing as the circuit size hierarchy. In 
particular, if we refer to Homework 2, Problem 1, for each $T(n) \leq 2^n / 
10n$, there exists a function whose size is $\Theta(T(n))$. Thus, there exists a 
language $L$ whose size is $\Theta(n^{\log n})$. Note that $L \in 
\size(O(n^{\log n}))$. Assume for the sake of contradiction that the original 
claim is false. Then, we have that $\size(O(n^{\log n})) \subseteq BPP \subseteq 
\size(\poly(n))$. However, we have just established that $L$ does not have a 
family of polynomial sized circuits. This contradiction establishes the claim.

\section*{Problem 4}

Given the premise of the problem, it remains to show that if there exists a $k$ 
such that we can $2$-approximate \#CSAT in $FP_{||}^{NP[k]}$, then there exists 
some $k'$ such that $P_{||}^{NP[k]} = P_{||}^{NP[k-1]}$.

It is conceivable that, taking the Hint to be true, one could use the number $t$ 
as a parameter passed to the NP oracle in a fashion similar to how it was done 
in Problem 2.

\end{document}
